package br.com.rookgraph;

import java.util.Stack;

import br.com.rookgraph.utils.ArrayUtils;

/**
 * Grafo com representação em armazenamento em Matiz.
 *
 * @author Luan Pontes
 * @since 11-9-12
 *
 */
public class Graph {

	/**	associações entre vertices (Arestas) **/
	private int[][] edges;

	/**	Número de Vertices **/
	public int order;

	public Graph(int order){
		this.order = order;
		this.edges = new int[order][order];
	}

	/**
	 * Adiciona uma associação entre vertices.
	 *
	 * @param origin origem
	 * @param target destino
	 * @param value  valor associação
	 *
	 */
	public void addEdge(int origin, int target, int value){
		if(isValid(origin, target)){
			setMatriz(origin, target, value);
			setMatriz(target, origin, value);
		}else{
			throw new IllegalArgumentException("Origin ("+origin+") or Target("+target+") invalid!( < 0 or > ordem )");
		}
	}

	public void addEdge(Edge edger){
		addEdge(edger.origin, edger.target, 1);
	}

	/**
	 * Remove uma associação entre vertices.
	 *
	 * @param origin origem
	 * @param target destino
	 *
	 */
	public void removeEdge(int origin, int target){
		if(isValid(origin, target)){
			setMatriz(origin, target, 0);
			setMatriz(target, origin, 0);
		}else{
			throw new IllegalArgumentException("Origin ("+origin+") or Target("+target+") invalid!( < 0 or > ordem )");
		}
	}

	public void removeEdge(Edge edger) {
		this.removeEdge(edger.origin, edger.target);
	}

	/**
	 * Verifica a existencia de uma Aresta.
	 *
	 * @param origin origem
	 * @param target destino
	 */
	public boolean hasEdge(int origin, int target){
		return isValid(origin, target) && getMatix(origin, target) != 0;
	}

	public boolean hasEdge(Edge edger){
		return hasEdge(edger.origin, edger.target);
	}

	/** Recupera o valor de uma Aresta.
	 * @param origin
	 * @param target
	 * @return valor da Aresta
	 */
	public int getEdge(int origin, int target){
		return isValid(origin, target) ? getMatix(origin, target) : 0;
	}

	/**
	 * @return ordem do grafo.
	 */
	public int getOrder(){
		return this.order;
	}

	/**
	 * Retorna o ALFA da aresta, ou seja, o número de
	 * branchs que a aresta incide.
	 *
	 * @param oring
	 * @param target
	 * @return
	 */
	
	public int alfa(int oring, int target){
		int quantBranch = 0;

		quantBranch += grau(oring) > 2 ? 1 : 0;
		quantBranch += grau(target) > 2 ? 1 : 0;

		return quantBranch;
	}

	/**
	 * Retorna se o vértice é branch (0 ou 1)
	 *
	 * @param oring
	 * @param target
	 * @return
	 */
	
	public int branch(int vertice){
		
		if (vertice != 0)
		    return grau(vertice) > 2 ? 1 : 0;
	  return vertice;
		
	}

	
	public int calcBranch(int v1, int v2, int v3, int v4){
		
		return branch(v1)+branch(v2)+branch(v3)+branch(v4);		
	}
	
	public int alfa(Edge edge){
		return alfa(edge.origin, edge.target);
	}

	 	
	/*
	 * Calcula a diferença entre branches DEPOIS-ANTES da troca
	 * Considera como parâmetros uma troca (2 arestas)
	 *
	 */
	// faz diferença calcular o diffbranch entre todos os vértices e usando apenas as trocas (cut e rep separadamente).
	// isso porque quando considero apenas a troca isolada, ela pode ser vantajosa
	// no entanto quando olho para os vértices envolvidos, pode não haver redução de brahch.

	public int diffBranch (Swap swap) {
		
			int qntBranchAnt = 0, qntBranchPos = 0;
		
		//	qntBranchAnt = this.alfa(swap.getCut()); 
			qntBranchAnt = this.alfa(swap.getCut())+this.alfa(swap.getReplace());
			this.swapEdge(swap);
		//	qntBranchPos = this.alfa(swap.getReplace());
			qntBranchPos = this.alfa(swap.getReplace())+this.alfa(swap.getCut());
			this.swapEdge(new Swap(swap.getReplace(), swap.getCut())); //troca invertida (desfaz a troca que foi feita acima)

			return qntBranchPos-qntBranchAnt;
		}

	
//	public int diffBranch (Swap swap) {
//		    int v1, v2, v3, v4;
//		    
//			v1 = swap.getCut().origin;
//			v2 = swap.getCut().target;
//			v3 = swap.getReplace().origin;
//			v4 = swap.getReplace().target;
//			
//			int qntBranchAnt = 0, qntBranchPos = 0;
//		
//			if (v1 == v3 || v2 == v3) 
//				qntBranchAnt = calcBranch(v1,v2,v4,0);
//			else{
//				if (v1 == v4 || v2 == v4) 
//					qntBranchAnt = calcBranch(v1,v2,v3,0);
//				else
//					qntBranchAnt = calcBranch(v1,v2,v3,v4);
//			}						 
//			
//			this.swapEdge(swap);
//			
//			if (v1 == v3 || v2 == v3) 
//				qntBranchPos = calcBranch(v1,v2,v4,0);
//			else{
//				if (v1 == v4 || v2 == v4) 
//					qntBranchPos = calcBranch(v1,v2,v3,0);
//				else
//					qntBranchPos = calcBranch(v1,v2,v3,v4);
//			}
//			
//			this.swapEdge(new Swap(swap.getReplace(), swap.getCut())); //troca invertida (desfaz a troca que foi feita acima)
//
//			return qntBranchPos-qntBranchAnt;
//		}

	

		
	/*
     * Calcula a diferença entre GAMA DEPOIS-ANTES da troca
	 * Considera como parâmetros uma troca (2 arestas)
	 *
	*/		
	public int diffGama (Swap swap) {
		return gama(swap, true) -  gama(swap, false);	
	}

	
	/*
	 * Inserção retorna maior grau entre os vértices
	 * Remoção retorna menor grau entre os vértice
	 *
	 */
	public  int gama(Swap swap, boolean isInsert) {
		
		// Calculando antes da da troca	
		int grauMin = grauEstrela(swap);
		
		// calculando gama apos a troca
		if (isInsert) {
			swapEdge(swap);
			grauMin = grauEstrela(swap);
			swapEdge(new Swap(swap.getReplace(), swap.getCut()));		
		}	
		return grauMin;
	}

	/* Retorna o grau estrela de um par de arestas,
	 * Ou seja, o grau mínmo de um par de arestas, considerando o ajustes de limiar para gruas 1 e 2
	 */
	
	public int grauEstrela(Swap swap) {
		
		int grauRep, grauCut;

		grauRep = getGrau(swap.getReplace());
		grauCut = getGrau(swap.getCut());
		
		return Math.min(grauRep, grauCut);	
	}

	private int getGrau(Edge edge) {
		int grauOriRep = edge.gama; 
		if (grauOriRep == 2) { 
			grauOriRep =  this.order;
		} else if (grauOriRep == 1) {
				grauOriRep =  this.order + 1; 			
		}
		return grauOriRep;
	}		
	
	
	public int lambda(Swap swap) {
		int lambdaTroca, sinalTroca;
		
		sinalTroca = -1;
	    if (diffGama(swap) > 0) {
	    	sinalTroca = 1;  
	    }
		lambdaTroca =  gama(swap, true)*sinalTroca; 
	
		return lambdaTroca;
	}

	
	
	
	/**
	 * Retorna o sigma de uma aresta, ou seja,
	 * o somatorio de dos graus que a aresta incide
	 * menos a própria aresta em questão.
	 *
	 * @param oring
	 * @param target
	 * @return
	 */
	public int sigma(int oring, int target){
		return grau(oring) + grau(target) - 2;
	}

	public int sigma(Edge edge){
		return this.sigma(edge.origin, edge.target);
	}

	
	
	/*
	 * Inserção qnt de vertices que passaram a ser branches.
	 * Remoção qnt de vertices que deixaram de ser branches.
	 *
	 */
	public int beta(Edge edge, boolean isInsert) {
		int qntBranchAnt, qntBranchPos;

		if (isInsert) {
			// A Remmoção da aresta abaixo justifica-se porque antes dessa chamada a aresta já foi adicionada
			// Como preciso saber os branches antes, tenho que remover para ver o impacto de beta
			this.removeEdge(edge);
			qntBranchAnt = alfa(edge);
			this.addEdge(edge);
			
			qntBranchPos = this.alfa(edge);
		} else {
			
			qntBranchAnt = this.alfa(edge);

			this.removeEdge(edge);
			qntBranchPos = alfa(edge);
			this.addEdge(edge);
		}

		return qntBranchPos - qntBranchAnt;

	}

		
	/*
	 * Inserção retorna maior grau entre os vértices
	 * Remoção retorna menor grau entre os vértice
	 *
	 */
	public  int gama(Edge edge, boolean isInsert) {

		int grauOrigin = 0;
		int grauTarget = 0;
		final int limiar = 3;
		
		//  Inserção da aresta
		if (isInsert) {
			this.addEdge(edge);
			grauOrigin = grau(edge.origin);
			grauTarget = grau(edge.target);
			this.removeEdge(edge);
			
			if (grauOrigin < limiar && grauTarget < limiar) 
				return Math.min(grauOrigin, grauTarget);
			
			else 
				return Math.max(grauOrigin, grauTarget);
		} else {
			 	grauOrigin = grau(edge.origin);
			 	grauTarget = grau(edge.target);
		
			 	if (grauOrigin >= limiar && grauTarget >= limiar) 
			 		return Math.min(grauOrigin, grauTarget);
			 	else 
			 		return Math.max(grauOrigin, grauTarget);
			}
		}

	
	
	
		
	/**
	 * Retorna o grau do vertice passado, ou seja, o
	 * número de aresta que o vertice possui.
	 * @param v
	 * @return
	 */
	
	//TODO Alterar para equivalente inglês.
	public int grau(int v) {
		return this.getAdjacentes(v).length;
	}

	public int[] getBranchs() {
		int[] branches = new int[this.order];
		int qntBranches = 0;
		for (int i = 1; i <= this.order; i++) {
			if(this.grau(i) > 2){
				branches[qntBranches++] = i;
			}
		}
		return ArrayUtils.copyNewArray(branches, qntBranches);
	}

	
	/**
	 * Retorna o grau máximo do grafo
	 */
	public int getGrauMax(Graph graph) {
		
		int grauMax = 0;
		for (int i = 1; i <= graph.order; i++) {
			grauMax = grauMax >= grau(i) ? grauMax : grau(i);
		}
		return grauMax;
	}
	
	
	/**
	 * Método gera uma Arvore a partir do grafo.
	 * Recebe um nó que será usado como 'raiz', dependendo da
	 * raiz a arvore tera uma formato diferente.
	 *
	 *   TODO verificar se isso acontece em para qualquer grafo.
 	 *
	 * @param graphTree grafo retornado que coterá a 'arvore'.
	 * @param root raiz utilizada no grafo.
	 *
	 * @return graphTree representado a arvore gerada.
	 */
	public Graph getTree(Graph graphTree, final int root){

		int[] adjacents = getAdjacentes(root);

		for (int vAdj = 0; vAdj < adjacents.length; vAdj++) {
			boolean hasTree = false;

			for (int vTree = 1; vTree <= this.order; vTree++) {

				if(graphTree.hasEdge(adjacents[vAdj], vTree)){
					hasTree = true;
					break;
				}
			}

			if(!hasTree){
				graphTree.addEdge(root, adjacents[vAdj], getMatix(root, adjacents[vAdj]));
				getTree(graphTree, adjacents[vAdj]);
			}
		}
		return graphTree;
	}

	public Graph getTreeLarge(Graph graphTree, final int root){

		Stack<Integer> pilha = new Stack<Integer>();

		pilha.push(root);

		int atual;
		while(!pilha.isEmpty()){
			atual = pilha.pop();

			for (Integer adj : this.getAdjacentes(atual)) {

				boolean hasTree = false;
				for (int vTree = 1; vTree <= this.order; vTree++) {

					if(graphTree.hasEdge(adj, vTree)){
						hasTree = true;
						break;
					}
				}
				if(!hasTree){
					graphTree.addEdge(atual, adj, getMatix(atual, adj));
					pilha.push(adj);
				}
			}
		}

		return graphTree;
	}

	//	TODO: Observar a frequência de uso deste método
	//	se for muito frequente, seria melhor pensar em uma
	//	nova representação para o grafo.
	public int[] getAdjacentes(int v) {
		int[] lineMatrix = new int[order];
		int count = 0;
		for (int j = 0; j < order; j++) {

			if(this.edges[v-1][j] != 0){
				lineMatrix[count++] = j+1;
			}

		}

		return ArrayUtils.copyNewArray(lineMatrix, count);
	}

	public int[] reached(int root, int[] list){

		int[] adjacents = getAdjacentes(root);

		int count = ArrayUtils.nextFree(list);

		list[count] = root;
		for (int vAdj : adjacents) {
			if(!ArrayUtils.conteinsList(vAdj, list)){
				reached(vAdj, list);
			}
		}
		count = ArrayUtils.nextFree(list);
		return ArrayUtils.copyNewArray(list, count);
	}


	/**
	 * Verifica se a origin e target são validos,
	 * se não lança uma  IllegalArgumentException.
	 * @param origin
	 * @param target
	 * @return
	 */
	public boolean isValid(int origin, int target) {
		if((origin > 0 && origin <= order) && (target > 0 && target <= order)){
			return true;
		}
		throw new IllegalArgumentException("Origin ("+origin+") or Target("+target+") invalid!( < 0 or > ordem )");
	}

	/**
	 * Mostra na saída padrão as associações do Grafo.
	 */
	public void showEdges(){
		for (int i = 0; i < this.edges.length; i++) {
			for (int j = 1; j < this.edges[0].length-1; j++) {

				if(this.edges[i][j] != 0 ){
					System.out.println( (i+1)+ "<--("+this.edges[i][j]+")-->"+(j+1));
				}
			}
		}
	}

	/**
	 * Mostra na saída padrão as associações do Grafo em
	 * forma de matriz.
	 */
	public void showMatix(){
		int value = 0;
		System.out.print("    ");
		for (int i = 0; i < this.edges.length; i++) {
			if (i<9) {
				System.out.print("|_"+(i+1)+"_");
			 }else {
				 System.out.print("|_"+(i+1)+"");
			    }
		}
		for (int i = 0; i < this.edges.length; i++) {
			if (i<9) {
				System.out.print("\n  "+(i+1));
			 }else {
				 System.out.print("\n "+(i+1));
			    }
			for (int j = 0; j < this.edges[0].length; j++) {

				 value = this.edges[i][j];
				 System.out.print(" | "+ ( value != 0 ? value : " "));
			}
		}
	}

	private void setMatriz(int origin, int target, int value) {
		if(isValid(origin, target))
			this.edges[origin-1][target-1] = value;
	}

	public int getMatix(int origin, int target) {
		return this.edges[origin-1][target-1];
	}

	public int[][] edges(){
		return this.edges;
	}

	@Override
	public Object clone() throws CloneNotSupportedException {
		Graph clone = new Graph(this.order);

		for (int i = 0; i < this.order; i++) {
			for (int j = 0; j < this.order; j++) {
				if(this.edges[i][j] != 0){
					clone.setMatriz(i+1, j+1, this.edges[i][j]);
				}
			}
		}

		return clone;
	}
	
	@Override
	public String toString() {
		String graphSt = "";
		for (int i = 0; i < this.edges.length; i++) {
			for (int j = 1; j < this.edges[0].length-1; j++) {
				if(i==j) break;
				if(this.edges[i][j] != 0 ){
					graphSt +="\n"+(i+1)+" "+(j+1);
				}
			}
		}
		return graphSt;
	}
	
	public void swapEdge(Swap swap){
		this.removeEdge(swap.getCut());
		this.addEdge(swap.getReplace());
	}

}


